package com.lwt.codetop.arrayOrSort;

// 88. 合并两个有序数组

import java.util.Arrays;

/**
 * 思路：归并排序的归并过程
 * 时间复杂度：O(n) 空间复杂度：O(n)，额外开一个暂存空间数组
 */
public class MergeSortedArray {
    private static int[] nums1;
    private static  int[] nums2;
    private static int[] tmp;
    public static void main(String[] args) {
        // 构建测试用例
        nums1 = new int[]{1,2,3,0,0,0};
        nums2 = new int[]{2,5,6};
        int n = 3, m = 3; // nums1和nums2的元素个数
        tmp = new int[n + m];

        // 归并过程
        merge(nums1, nums2, n, m);
        // 输出归并后的结果 在nums1中
        for (int x : nums1) {
            System.out.print(x + " ");
        }
    }

    /**
     * 合并两个有序的数组，结果保存在nums1中
     * @param nums1
     * @param nums2
     * @param n
     * @param m
     */
    private static void merge(int[] nums1, int[] nums2, int n, int m){
        int i = 0, j = 0, k = 0;
        // 归
        while(i < n && j < m) {
            if(nums1[i] <= nums2[j]){
                tmp[k ++] = nums1[i];
                i += 1;
            }else {
                tmp[k ++] = nums2[j];
                j += 1;
            }
        }
        // 扫尾
        while(i < n){
            tmp[k ++] = nums1[i];
            i += 1;
        }
        while(j < m){
            tmp[k ++] = nums2[j];
            j += 1;
        }
        // 还原结果
        for (int l = 0; l < n + m; l++) {
            nums1[l] = tmp[l];
        }
    }
}
